18185. Give away

You are given a 1-indexed array X, consisting of n integers, and a set of q queries. There are two kinds of queries:

0 a b c – here you are required to return the number of elements with indices in [a, b] greater than or equal to c;

1 a b – here you are required to change the ath element of array to b.

Input. First line contains n, the number of elements in the array X. The next line contains n integers representing the elements of X. The third line contains a single integer q – the number of queries. The next q lines each contain queries of two kinds as described above. All the elements of array and the update values are distinct.

Output. Print q lines, the i-th line contains the answer for the i-th query.

Sample input	Sample output
5 1 2 3 4 5 3 0 1 5 10 1 2 20 0 1 3 10	0 1

РЕШЕНИЕ

SQRT декомпозиция

Анализ алгоритма

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <set>

#include <algorithm>

#include <cmath>

using namespace std;

vector<int> a;

vector<vector<int> > b;

int i, n, q, len, blocks, l, r, x, type;

int idx, val;

int query(int l, int r, int x)

{

int res = 0;

int c_l = l / len, c_r = r / len;

if (c_l == c_r)

{

for (i = l; i <= r; i++)

if (a[i] >= x) res++;

}

else

{

for (i = l; i <= (c_l + 1)*len - 1; i++)

if (a[i] >= x) res++;

for (i = c_l + 1; i <= c_r - 1; i++)

res += b[i].end() - lower_bound(b[i].begin(), b[i].end(), x);

for (i = c_r * len; i <= r; i++)

if (a[i] >= x) res++;

}

return res;

}

int main(void)

{

scanf("%d", &n);

a.resize(n);

len = sqrt(n) + 1;

blocks = ceil((double)n / len);

b.resize(len);

for (i = 0;i < n; i++)

{

scanf("%d", &a[i]);

b[i / len].push_back(a[i]);

}

scanf("%d", &q);

for (i = 0;i < blocks; i++)

sort(b[i].begin(), b[i].end());

while (q--)

{

scanf("%d", &type);

if (type == 0)

{

scanf("%d %d %d", &l, &r, &x);

printf("%d\n", query(l - 1, r - 1, x));

}

else

{

scanf("%d %d", &idx, &val);

idx--;

int block = idx / len;

int initVal = a[idx];

int pos = lower_bound(b[block].begin(), b[block].end(), initVal)

- b[block].begin();

b[block][pos] = val;

a[idx] = val;

sort(b[block].begin(), b[block].end());

}

}

return 0;

}